package kyssion.leetcode.num201_250;

import kyssion.leetcode.util.TreeNode;

public class code222_完全二叉树的节点个数 {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    //递归求解，最简单的实现
    /*
    public int countNodes(TreeNode root) {
        if(root == null)
            return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    */

    //二分法，非常有灵性的实现
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        int leftD = depth(root.left);
        int rightD = depth(root.right);
        if (leftD == rightD)
            return (1 << leftD) + countNodes(root.right);
        else
            return (1 << rightD) + countNodes(root.left);

    }

    public int depth(TreeNode node) {
        int d = 0;
        while (node != null) {
            d++;
            node = node.left;
        }
        return d;
    }
}
